The present invention relates generally to memory addressing schemes in computer systems, and specifically, to a cache directory structure and cache memory access method for reducing memory access latency in systems employing multiple cache memory levels.
The design and use of caches in computer systems is a well-known and widely studied area in the field of memory hierarchy design (for example, see the text books High Performance Computer Architecture, by Harold Stone, third edition, Addison-Wesley, 1993, chapter 2 (herein referred to as xe2x80x9cStonexe2x80x9d), and Computer Architecture A Quantitative Approach, by John Hennessy and David Patterson, second edition, Morgan Kaufman, 1996, chapter 5). Presently, typical computer systems have two levels of caching, where the caches are referred to as the L1 and L2 caches, above main memory. The units of transfer between the L1 and L2 caches, and between the L2 cache and main memory, are referred to as cache lines. Today, typical computer systems have a fixed line size, usually with the same line size for the L1 and L2 caches.
As main memory sizes increase, a third level (L3) cache may become necessary for efficient operation. The L3 cache may have a larger line size than that of the L1 and L2 caches. Furthermore, in computer system designs that utilize main memory compression, logically fixed size units in main memory are automatically stored in compressed form and decompressed on cache misses. In such designs, the logically fixed size units of main memory occupy varying amounts of space (due to compression). A number of techniques for efficiently storing and accessing variable size units of compressed data in main memory are now known, for example, and described in: commonly-owned U.S. Pat. No. 5,761,536 entitled SYSTEM AND METHOD FOR REDUCING MEMORY FRAGMENTATION BY ASSIGNING REMAINDERS TO SHARE MEMORY BLOCKS ON A BEST FIT BASIS; commonly-owned U.S. Pat. No. 5,864,859, entitled SYSTEM AND METHOD OF COMPRESSION AND DECOMPRESSION USING STORE ADDRESSING; and, a reference authored by P. Franaszek and J. Robinson entitled DESIGN AND ANALYSIS OF INTERNAL ORGANIZATIONS FOR COMPRESSED RANDOM ACCESS MEMORIES, IBM Research Report RC 21146, IBM Watson Research Center, Oct. 20, 1998.
In the case where main memory is compressed, it is natural to identify the unit of compression as a line size; for purposes of description, in a computer system with three levels of caching (L1, L2, L3), the main memory will be referred to as L4, and the unit of compression will be referred to as the L4 line size. As an example, the L1 and L2 caches could have line sizes of 64 bytes, the L3 cache could have a line size of 256 bytes, and L4 (main memory) could have a line size (that is, size of the unit of compression) of 1024 bytes. FIG. 1 illustrates a cache/memory hierarchy with CPU 110, main memory Ln 160, and multiple cache levels Li 120, Lixe2x88x921 130, Li 140, Lnxe2x88x921 150.
FIG. 2 illustrates a conventional cache directory 210 for a 4-way set associative cache that implements a 4-way content addressable memory 220 to determine whether a line corresponding to a given memory address is currently stored in the cache, and if so, its location and status. To determine whether Lixe2x88x921 includes a line of size s (s=256 bytes, for example) corresponding to a CPU generated address xe2x80x9cAxe2x80x9d, e.g., a 32-bit or 64-bit address, including tag bits 200 (xe2x80x9ctagxe2x80x9d) and offset bits 201 (xe2x80x9coffsetxe2x80x9d), the set 215 corresponding to the offset 201 (in this example j) is found in the Lixe2x88x921 cache directory 210, and the tag 200 is compared to all tags 216, 217, 218, 219 in set 215 of the Lixe2x88x921 cache directory 210 using a 4-way content addressable memory 220 (i.e., comparators). As a result of the comparison, there will be generated either 0 or 1 matches, and if a match exists, the index of the match is used to find the corresponding line of size s in cache Lixe2x88x921. Once the line is found, it is gated to a cache output-data buffer for use by the system/processor. FIG. 2 corresponds to the cache directory portion as illustrated in FIG. 2-7 on page 38 of Stone.
Referring back to FIG. 1, due to possible differences in line sizes between L2 and L3 caches, and between L3 and L4 (main memory), certain problems in efficient operation may occur. In an example scenario, consideration is given to the interface between L3 cache and L4 in the case that main memory (L4) is compressed, and with line sizes as in the previous example. Additionally, it is assumed that caches are of the store-in type, that is, when a line in L3 cache is replaced, if the line is marked as modified, it is necessary to first write the line to L4 (referred to as a writeback). Since the L4 lines are compressed and of size 1024 bytes (when uncompressed), and given that the L3 cache lines are of size 256 bytes, this may involve decompressing the L4 line, performing the writeback (i.e., writing the appropriate 256 byte section of the 1024 byte uncompressed L4 line using the modified data in the 256 byte L3 line), and then re-compressing the L4 line. If a sequence of L3 writebacks from different modified L3 lines occur to the same L4 line, this would involve repeated decompressions and re-compressions for the same L4 line, which may result in excessive overhead. An approach for solving this problem is as follows: at the time the L3 line is written back, find all other modified L3 lines residing in the same L4 line, and write back all such L3 lines; that is, xe2x80x9cbatchingxe2x80x9d L3 writebacks. However, current techniques for cache directory design may result in this being an expensive operation. As described in the previously cited text book by Stone for example, a cache directory may be organized using a number of associativity sets, and a content addressable memory may be used to determine whether a line with a given address is in the cache in the associated set (see Stone, Section 2.2.2, pages 36-44). Using the usual mapping of addresses to sets, the four consecutive 256 byte L3 lines residing in a 1024 byte L4 line will be in four consecutive sets. In order to check whether each line is in the L3, and if so, whether it is modified, the L3 cache directory must be accessed four times. This problem is made worse for increasing differences between L3 and L4 line sizes. For example, with a 64 byte L3 line size, the L3 cache directory would have to be accessed 16 times in order to find all modified L3 lines residing in a given 1024 byte L4 line (because 16xc3x9764=1024).
Similar problems occur in certain situations even when there is no memory compression. Consider the previous example of an L3 line size of 256 bytes and an L2 line size of 64 bytes. It has been found advantageous, in memory hierarchy design, due to considerations having to do with cache coherency in multiprocessor designs and correct functioning of the I/O system in both uniprocessor and multiprocessor designs, to incorporate a principle known as inclusion. This is defined in the previously referenced text book by Hennessy and Patterson as follows (page 723):
every level of cache hierarchy is a subset of the level further away from the processor.
In the context of the current example, inclusion requires that when a 256 byte line is replaced in the L3, if any of the four 64 byte lines residing in the 256 byte line are currently present in the L2 (or in a multiprocessor system with multiple L2 caches, each for a different processor, any such L2), these lines must be marked as invalid (with a writeback required before invalidation if the line is marked as modified). As in the previous example, using current cache design techniques, this requires four L2 cache directory accesses (or in a multiprocessor system, four L2 cache directory accesses for every L2 cache). As before, this problem is made worse with increasing differences between L2 and L3 line sizes.
It would thus be highly desirable, in a computer system with multiple levels of caches L1, L2, . . . , Lnxe2x88x921 and main memory Ln and in which for some level of the memory hierarchy Lixe2x88x921 the line size s of Lixe2x88x921 is smaller than the line size t of Li, to provide a mechanism whereby all lines in Lixe2x88x921 that reside in any given line in Li can be found quickly and efficiently without requiring multiple accesses (t/s accesses are required in the above examples) to the cache directory of Lixe2x88x921.
It is an object of the present invention to provide in a computer system having a processor, a memory system including multiple levels of caches L1, L2, . . . , Lnxe2x88x921 and including main memory Ln, and in which the cache Lixe2x88x921 includes lines of size s and the cache Li includes lines of size t with t greater than s, a dual line size cache directory structure for the contents of a cache level Lixe2x88x921 that, in addition to determining (as conventional) whether Lixe2x88x921 includes a line of size s corresponding to an address and if so its location and status, the additional ability to determine whether cache level Lixe2x88x921 contains any of the t/s lines of size s residing in the larger line of size t corresponding to the address, and if so their locations and status in cache level Lixe2x88x921 without multiple accesses to the cache Lixe2x88x921 directory structure.
It is a further object of the present invention to provide a dual line size cache directory structure as in the previous object that further includes a batched writeback mechanism responsive to determination of a single line of size s in cache level Lixe2x88x921 having a modified status for determining whether there exists other (t/s)xe2x88x921 lines of size s residing in the larger line of size t that have a modified status, and concurrently writing back the one or more lines of size s that have been modified in the cache level Lixe2x88x921 to the cache level Li.
Thus, according to the principles of the invention, there is provided in a computer system having a processor, a memory system including multiple levels of caches L1, L2, . . . , Lnxe2x88x921 and including main memory Ln, and in which the cache Lixe2x88x921 includes lines of size s and the cache Li includes lines of size t with t greater than s, a cache directory system for the contents of cache Lixe2x88x921 comprising a dual line size cache directory structure including a first device for determining whether the cache Lixe2x88x921 includes a line of size s corresponding to an address, and, a second device for determining whether the cache Lixe2x88x921 includes any of the t/s lines of size s residing in the larger line of size t corresponding to the address in the cache level Li without multiple accesses to the cache Lixe2x88x921 directory structure. The second device further utilizes tag and offset information provided in the address for determining the locations and status of each t/s lines of size s residing in the larger line of size t without multiple accesses to the cache Lixe2x88x921 directory structure. The cache directory may be implemented in systems whereby a lowest level Li comprises compressed or uncompressed memory.
Advantageously, the dual line size cache directory structure may be used to effectively implement the inclusion property whereby, in response to eviction of a line of size s in cache level Lixe2x88x921 that is to be replaced with new data contents, the status of each of smaller lines residing in a cache level Lixe2x88x922 may be concurrently modified as being invalid without multiple accesses to a cache level Lixe2x88x922 directory.